
class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int size1 = cost.size(), size2 = cost.get(0).size(), mask = 1 << size2, INF = 0x3f3f3f3f;
        // 预处理
        int[] info = new int[size2];
        for(int i = 0;i < size2;i++){
            int min = INF;
            for(int j = 0;j < size1;j++){
                min = Math.min(min, cost.get(j).get(i));
            }
            info[i] = min;
        }
        // dp[i][state] 表示考虑集合1中的前i个点, 此时集合2中的连接情况为state(0表示未连接, 1表示连接), 此时的最小成本
        int[][] dp = new int[size1 + 1][mask];
        Arrays.fill(dp[0], INF);
        dp[0][0] = 0;
        for(int i = 1;i <= size1;i++){
            for(int state = 0;state < mask;state++){
                dp[i][state] = INF;
                for(int j = 0;j < size2;j++){
                    // 连到集合2中的j这个点上, 即使集合2中j这个点之前已经有集合1中的点连过, 也没事, 也可以继续连
                    dp[i][state] = Math.min(dp[i][state], dp[i - 1][state & (~(1 << j))] + cost.get(i - 1).get(j));
                }
            }
        }
        int min = INF;
        for(int state = 0;state < mask;state++){
            int cur = dp[size1][state];
            // 枚举state, 找到集合2中还没有连到集合1上的点, 然后找一个成本最小的连上
            for(int i = 0;i < size2;i++){
                if(((state >> i) & 1) == 0) cur += info[i];
            }
            min = Math.min(min, cur);
        }
        return min;
    }
}
